import java.sql.Array;
import java.util.LinkedList;
import java.io.*;
import java.util.*;


/**
 *   SecondChanceAlgorithm
 *   Class constructor. Also runs the experiment on the page references given in memString
 *	 The memory is represented as a linked list, ordered by time of reference so the head is the
 *	 oldest and the tail the most recent. Note that you may need a different memory representation
x*	 for your algorithms.
 */

public class SecondChanceAlgorithm
{

	public SecondChanceAlgorithm(int memSize, int memString[])
	{
		// The usual initialization.
		_pageFaults = 0;
		_memory = new LinkedList();
		_memSize = memSize;

        
        _pageTable = new boolean[50000];  //array sem heldur utan um page table og reference bit

		// Run our experiment
		for (int i = 0; i < memString.length; i++)
        {
			memAccess(memString[i]);
        }
	}


	//
	// memAccess
	//
	// Access a virtual memory page. We count a page fault if the virtual page is not in
	// memory.
	//
	private void memAccess(int page)
	{
		if (!_memory.contains(new Integer(page))){
            _pageTable[page] = true;   //set the reference bit
			pageFault(page);
        }

        else {
            _pageTable[page] = false;  //if page is in memory we clear the reference bit

            try
            {
                //we than remove the old page and insert the new one
                _memory.removeFirstOccurrence(page);
                _memory.addLast(new Integer(page));
            }
            catch(Exception ex)
            {
                ex.getMessage();
            }
        }
	}

	//When pageFault is processed it uses the FIFO ability
	private void pageFault(int page)
	{
		_pageFaults++; // Increment the page fault counter.

		// Check if there is space in our memory -- free page frames.
		if (_memSize == _memory.size())
			_memory.removeFirst();
       try
       {
		_memory.addLast(new Integer(page));
       }
       catch(Exception ex)
       {
           ex.getMessage();
       }
	}

	//
	// pageFaults
	//
	// Give the total page faults generated in the experiment
	//
	public int pageFaults()
	{
		return _pageFaults;
	}

	private LinkedList _memory;		// The simulated memory
	private int _memSize;			// Memory size in page frames
	private int _pageFaults;		// Page fault count
    private boolean[] _pageTable;        // reference bit

}

